object Fibonacci
{
	def main() : Unit = 
	{
		println("Let's compute and print the first 10 numbers of the Fibonacci sequence :" + 
		"	1. Recursive Fibonacci -> " + new RecursFibonacci().toString(10) +
		"	2. Iterative Fibonacci -> " + new IterFibonacci().toString(10));
	}
}

// Abstract class : should not be instantiated !
class AbstractFibonacci
{
	def toString(count : Int) : String = 
	{
		var i : Int;
		var array : Int[];
		var szRet : String;
		i = 0;
		array = this.compute(count);
		szRet = "{";
		
		while(i < count)
		{
			szRet = szRet + " " + array[i];
			if(!(i == count-1)) { szRet = szRet + ","; }
			i = i+1;
		}
		
		szRet = szRet + " }";
		
		return szRet;
	} 
	
	/* to be overridden */
	def compute(count : Int) : Int[] = { return new Int[0]; }
}

class RecursFibonacci  extends AbstractFibonacci
{
	def compute(count : Int) : Int[] =
	{
		var i : Int;
		var nRetArray : Int[];
		i = 0;
		nRetArray = new Int[count];
		
		while(i < count)
		{
			nRetArray[i] = this.fib(i);
			i = i+1;
		}
		
		return nRetArray;
	}
	
	/* returns the ith number of fibonacci sequence */
	def fib(i : Int) : Int = 
	{
		var nRet : Int;
		if(i < 2) { nRet = 1; }
		else { nRet = this.fib(i-1) + this.fib(i-2); }
		return nRet;
	}
}

class IterFibonacci extends AbstractFibonacci
{
	def compute(count : Int) : Int[] =
	{
		var i : Int;
		var nRetArray : Int[];
		i = 2;
		nRetArray = new Int[count];
		nRetArray[0] = 1;
		nRetArray[1] = 1;
		
		while(i < count)
		{
			nRetArray[i] = nRetArray[i-1] + nRetArray[i-2];
			i = i+1;
		}
		
		return nRetArray;
	}
} 